/*
 * PegGameAI.java
 *
 * Created on October 4, 2007, 10:55 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package peggame;

import java.util.ArrayList;
import java.util.Arrays;

/**
 *
 * @author Eric Drucker
 */
public class PegGameAI
{
	
	/** Creates a new instance of PegGameAI */
	public PegGameAI()
	{
	}
	
	/**
	 * Returns a list of all available moves based on the given board position
	 * @param pegs A board position
	 * @return Arraylist of possible moves
	 */
	public ArrayList<int[][]> getAvailableMoves(boolean [][] pegs)
	{
		ArrayList<int[][]> moveList = new ArrayList<int [][]>();
		
		//for each hole
		//if there is a peg
		//see if it can make a move (some will have more than one) NE, E, SE, SW, W, NW
		
		for(int i = 0; i < PegGameDATA.BOARD_SIZE; i++)
		{
			for(int j = 0; j < pegs[i].length; j++)
			{
				if(pegs[i][j])	//if there is a peg
				{					
					//NORTHEAST
					if(i > 1)
					{
						if(j < pegs[i-2].length)
						{
							if(pegs[i-1][j] && !pegs[i-2][j])
							{
								moveList.add(new int[][] {{i,j}, {i-2, j}});
							}
						}
					}
					//EAST
					if(j < pegs[i].length-2)
					{
						if(pegs[i][j+1] && !pegs[i][j+2])
						{
							moveList.add(new int[][] {{i,j},{i,j+2}});
						}
					}
					
					//SOUTHEAST
					if(j < pegs[i].length)
					{
						if(i < PegGameDATA.BOARD_SIZE-2)
						{
							if(pegs[i+1][j+1] && !pegs[i+2][j+2])
							{
								moveList.add(new int[][] {{i,j}, {i+2, j+2}});
							}
						}
					}
					
					//SOUTHWEST
					if(i < PegGameDATA.BOARD_SIZE-2)
					{
						if(pegs[i+1][j] && !pegs[i+2][j])
						{
							moveList.add(new int[][] {{i,j}, {i+2,j}});
						}
					}
					
					
					//WEST
					if(j > 1)
					{
						if(pegs[i][j-1] && !pegs[i][j-2])
						{
							moveList.add(new int[][] {{i,j},{i, j-2}});
						}
					}
					
					//NORTHWEST
					if(j > 1)
					{
						if(i > 1)
						{
							if(pegs[i-1][j-1] && !pegs[i-2][j-2])
							{
								moveList.add(new int[][] {{i,j},{i-2,j-2}});
							}
						}
					}
				}
			}
		}
		
		return moveList;
	}
	
	/**
	 * Finds the best possible move based on the current board position
	 * @param pegs The given board position
	 * @return The best available move
	 */
	public int[][] getNextMove(boolean [][] pegs)
	{
		int [][] nextMove = new int[2][2];
		
		int minPegsSoFar = 15;
		
		ArrayList<int[][]> possibleMoves = getAvailableMoves(pegs);
		
		for(int i = 0; i < possibleMoves.size(); i++)
		{
			int[][] tempMove;
			tempMove = possibleMoves.get(i);
			
			int xDiff = (tempMove[1][0] - tempMove[0][0])/2;
			int yDiff = (tempMove[1][1] - tempMove[0][1])/2;
			
			boolean[][] newPegs = new boolean[pegs.length][];
			
			for(int j = 0; j < pegs.length; j++)
			{
				newPegs[j] = new boolean[pegs[j].length];
				for(int k = 0; k < pegs[j].length; k++)
				{
					newPegs[j][k] = pegs[j][k];
				}
			}
			
			newPegs[tempMove[0][0]][tempMove[0][1]] = false;
			newPegs[tempMove[0][0]+xDiff][tempMove[0][1]+yDiff] = false;
			newPegs[tempMove[1][0]][tempMove[1][1]] = true;
			
			int numPegs = getMinPegsLeft(newPegs);
			
			if(numPegs == 1)
			{
				return tempMove;
			}
			else if(numPegs < minPegsSoFar)
			{
				minPegsSoFar = numPegs;
				nextMove[0] = Arrays.copyOf(tempMove[0], 2);
				nextMove[1] = Arrays.copyOf(tempMove[1], 2);
			}
		}
		
		
		return nextMove;
	}
	
	/**
	 * Recursive function to find a tree of moves to leave as few pegs as possible based on the current board position
	 * @param pegs The given board position
	 * @return The least possible number of pegs left
	 */
	public int getMinPegsLeft(boolean [][] pegs)
	{
		int minPegsSoFar = 15;
		
		ArrayList<int[][]> possibleMoves = getAvailableMoves(pegs);
		
		if(possibleMoves.size() == 0)
		{
			return numPegsLeft(pegs);
		}
		
		else
		{
			for(int i = 0; i < possibleMoves.size(); i++)
			{
				int[][] tempMove;
				tempMove = possibleMoves.get(i);
				
				int xDiff = (tempMove[1][0] - tempMove[0][0])/2;
				int yDiff = (tempMove[1][1] - tempMove[0][1])/2;
				
				boolean[][] newPegs = new boolean[pegs.length][];
				
				for(int j = 0; j < pegs.length; j++)
				{
					newPegs[j] = new boolean[pegs[j].length];
					for(int k = 0; k < pegs[j].length; k++)
					{
						newPegs[j][k] = pegs[j][k];
					}
				}
				
				newPegs[tempMove[0][0]][tempMove[0][1]] = false;
				newPegs[tempMove[0][0]+xDiff][tempMove[0][1]+yDiff] = false;
				newPegs[tempMove[1][0]][tempMove[1][1]] = true;
			
				int numPegs = getMinPegsLeft(newPegs);
				
				if(numPegs == 1)
				{
					return 1;
				}
				
				else if(numPegs < minPegsSoFar)
				{
					minPegsSoFar = numPegs; 
				}
			}
			
			return minPegsSoFar;
		}
	}
	
	/**
	 * Returns the number of pegs on the board
	 * @param pegs The current board
	 * @return The number of pegs in the board
	 */
	public int numPegsLeft(boolean [][] pegs)
	{
		int numPegs = 0;
		
		for(int i = 0; i < PegGameDATA.BOARD_SIZE; i++)
		{
			for(int j = 0; j < pegs[i].length; j++)
			{
				if(pegs[i][j])
				{
					numPegs++;
				}
			}
		}
		
		return numPegs;
	}
	
	
}
